#include <stdio.h>
#include <stdlib.h>
// #include <string.h>

int Majorty(int A[], int n){
    int i,c,count=0; //c用来保存候选主元素， count 用来计数
    c = A[0]; //／／设置 A[O］为候选主元素
    for (int i = 0; i < n; i++) //／／查找候选主元素
    {
        if(A[i] == c)
            count++; //／／对A 中的候选主元素计数
        else
            if(count>0) //／／处理不是候选主元素的情况
                count--;
            else{ //／／更换候选主元素， 重新计数
                c=A[i];
                count=1;
            }
    }
    if (count>0)
        for (i=count= 0; i < n; i++) //／／统计候选主元素的实际出现次数
            if(A[i] == c)
                count++;
    if(count>n/2) return c; //／／确认候选主元素
    else return -1; //／／不存在主元素
}

int main(){ //测试
    // int A[] = {5,5,5,5,7,7,7,5}; //有主元素的数组
    int A[] = {0,5,5,3,5,7,5,1}; //无主元素的数组
    int maj = Majorty(A,8);
    char out[20];
    // *out = maj > -1? "There is not major element" :"The major element is:";
    // printf("%s%d.\n", &out,maj);
    printf("The major element is:%d\n",maj);
    system("pause");
}
